package leetcode.l0616;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
 * 返回满足题意的二叉搜索树的种数。
 * @author Retain
 * @date 2021/6/16 19:46
 */
public class 不是很明白的Medium_不同的二叉搜索树_96 {

    public static void main(String[] args) throws ClassNotFoundException {

    }
    /**
     * 动态规划。比n小的构建左子树，比n大的构建右子树。不断递归。dp[i]表示1到i可以构建多少种树
     * dp[i]= dp[j] + dp[i-j-1] （构建左子树用掉前j个数字，则构建右子树需要用掉总共i-根节点1-左子树j=i-j-1）
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] dp = new int[n + 1] ;
        dp[0] = 1;
        dp[1] = 1;
        for (int i =2;i<=n;i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}
